This disclosure relates generally to methods of optimizing meshes in computer simulations, and more specifically to methods for reducing singularities in quadrilateral meshes.
Use of computer aided design (CAD) tools is common in the engineering industry and also finds use in theatrical animation and graphics. One critical component of CAD tools is the ability to create a three-dimensional collection of polygons, called a “mesh,” over a complex structure so that further analysis of the structure can be accomplished. That is, subsequent computing operations may be performed using the mesh as a substitute for the structure.
In 2D, the polygons in a mesh can be any combination of triangles, quadrilaterals, and polygons with five or more sides. In 3D, the mesh can be a combination of tetrahedral and hexahedral elements. There are many applications, especially in non-linear structural mechanics, linear elastic simulations, higher order spectral methods, and texture mapping, which are sensitive to the directions, curvatures, and features on the geometric models. In such applications, an all-quadrilateral and all-hexahedral mesh is often preferred over a triangular mesh. A good quadrilateral mesh is characterized by both topological and geometric quality metrics. Geometric quality is measured from metrics such as aspect ratio, min/max angles, area, etc. Topological quality is measured by regularity in vertex distribution. An internal vertex is considered “regular” if it has four incident edges, otherwise it is a “singular” node, or a “singularity.”
The Gauss-Bonnet theorem states that all surfaces with positive genus must have singularities. In addition, singularities are essential in controlling distortions near bifurcations, protrusions, cavities etc. and in abrupt shape transitions. However, singularities in mesh could lead to (1) numerical instability in computational fluid dynamics (CFD) applications (2) wrinkles in subdivision surfaces, (3) irrecoverable element inversions near concave boundaries, (4) helical patterns, (5) visible seams in texture maps, and (6) breakdown of structured patterns on manifolds. Therefore, the major challenges in producing high-quality quad and hex mesh generators are usually related to minimization and placement of singularities.
There are several automatic mesh generators that can produce a high geometric quality mesh. However, the resulting mesh is typically of low topological quality—specifically, the mesh is not optimized with respect to singularities—which is detrimental in the downstream analysis or graphics applications. There are no known techniques to create meshes with both high geometric and high topological qualities, but having such a mesh is critical to producing the fastest, and most accurate, finite element analysis (FEA). Similarly, there are several techniques today that assist in mesh improvement, mesh refinement and mesh simplification. However, while these yield meshes with acceptable geometric quality, they provide very limited control over topological quality.
Further, quad and hex meshes are inherently global in nature: a single modification to their topology can have a domino effect, in that a large number of elements may have to undergo modifications to keep the mesh consistent. The non-localness compounds difficulties in the automation of quad mesh generation and editing, as various quality criteria have non-linear dependencies which can be extremely hard to encode and solve. Furthermore, it is also impossible to refine, coarsen, or edit a quad mesh with local operations, as they create additional singularities. For all these reasons, quad and hex meshing problems are often formulated as global optimization problems. Unfortunately, these optimizations are expensive, and their parametric tweaking is non-intuitive. There is no direct intuitive connection between the user constraints and the resulting mesh topology.
While there have been some significant developments in automatic quadrilateral mesh generation, a robust framework for addressing both geometric and topological quality is needed. Therefore, the purpose of this disclosure is to provide a methodology for reducing singularities in a quadrilateral mesh without loss of geometric quality.